from typing import *


class Solution:
    def countPartitions(self, nums: List[int], k: int) -> int:
        mod = 1000000007
        n = len(nums)
        f = [[0] * (k + 1) for _ in range(n + 1)]
        f[0][0] = 1
        sm = 0
        for i in range(1, n + 1):
            num = nums[i - 1]
            for j in range(k + 1):
                f[i][j] = f[i - 1][j]
                if j - num >= 0:
                    f[i][j] += f[i - 1][j - num]
        for i in range(k):
            sm += f[n][i]
        print(pow(2, len(nums), mod), sm)
        return pow(2, len(nums), mod) - sm * 2


s = Solution()
print(s.countPartitions([96, 40, 22, 98, 9, 97, 45, 22, 79, 57, 95, 62], 217))
print(s.countPartitions([96, 40, 22, 98, 9, 97, 45, 22, 79, 57, 95, 62], 505))
# print(s.countPartitions(nums=[1, 2, 3, 4], k=4))
